package main

/**
 *
 * @param n int整型
 * @return string字符串一维数组
 */
func generateParenthesis(n int) []string {
	// write code here
	dfs(0, 0, []byte{}, n)
	return rs
}

var rs []string

func dfs(left, right int, path []byte, n int) {
	if left == right && left == n {
		rs = append(rs, string(path))
		return
	}
	if left < n {
		dfs(left+1, right, append(path, '('), n)
	}
	if left > right {
		dfs(left, right+1, append(path, ')'), n)
	}
}
